class Solution {
public:
    const static int mod = 1e9 + 7;
  //  typedef unsigned long long ull;
    int checkRecord(int n) {
        if(n == 1) return 3;
        vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(2,vector<int>(3)));
        dp[0][0][0] = 1;
        
        for(int i = 1;i <= n;i++){
            for(int j = 0;j < 2;j++){
                for(int k = 0;k < 3;k++){
                    if(j == 1 && k == 0){ 
                      dp[i][j][k] = (dp[i][j][k]+dp[i-1][j-1][0])%mod;
                      dp[i][j][k] = (dp[i][j][k]+dp[i-1][j-1][1])%mod;
                      dp[i][j][k] = (dp[i][j][k]+dp[i-1][j-1][2])%mod;
                    }
                    
                    if(k != 0){
                      dp[i][j][k] = (dp[i][j][k]+dp[i-1][j][k-1])%mod;
                    }
                    
                    if(k == 0){
                      dp[i][j][k] = (dp[i][j][k]+dp[i-1][j][0])%mod;
                      dp[i][j][k] = (dp[i][j][k]+dp[i-1][j][1])%mod;
                      dp[i][j][k] = (dp[i][j][k]+dp[i-1][j][2])%mod;
                    }
                }
            }
        }

        int ret = 0;
        for(int j = 0;j < 2;j++){
            for(int k = 0;k < 3;k++){
                ret += dp[n][j][k];
                ret %= mod;
            }
        }
        return ret;
    }
};
